\section{Density-based objective}
\label{sec:theory1}
In this section, we claim that {\it Density-sTF} and {\it Density-mTF} are NP-hard problems. We then present the algorithms {\it s-DensestAlk} (Algorithm ~\ref{algo:sDlk})  and {\it m-DensestAlk} (Algorithm ~\ref{algo:mDlk}) for {\it Density-sTF} and {\it Density-mTF}, respectively. Further, we prove that {\it Density-sTF} achieves 3-approximation factor. 

\begin{theorem}
{\it Density-sTF} and {\it Density-mTF} problems are NP-complete.
\end{theorem}
\begin{proof}
We prove the $claim$ by a reduction from the {\it Densest at least $k$ subgraph (DalkS)} problem defined in ~\cite{KS}. An instance of {\it DalkS} consists of a graph $G({\cal X}, E)$, and a constant $k$, and the solution is a maximum density subgraph with at least $k$ nodes. We transform it into an instance of {\it Density-sTF} problem by defining a skill $a$ for every node $v \in V$ in which case a solution would be a maximum density subgraph with at least $k$ nodes that have skill $a$. And since skill $a$ is defined for every node in $G$, it is easy to see that ${\cal X'} \subseteq {\cal X} $ is the solution to the problem {\it Density-sTF}  iff it is a solution to the problem {\it DalkS}. The problem {\it Density-sTF} is a special case of {\it Density-mTF} which implies that {\it Density-mTF} is NP-hard. 
\end{proof}

\subsection{3-approximation algorithm for {\it Density-sTF}}
\label{subsec:density-sTF}
{\it Intuition}: To begin with, the algorithm {\it s-DensestAlk} (Algorithm ~\ref{algo:sDlk}) accepts the graph and the skill requirements as an input. It then finds the densest subgraph and removes it from the input graph and adds it to the solution subgraph (which is initially empty). It then checks if the solution subgraph satisfies the skill  requirements. Until the solution subgraph constructed meets the skill requirements, the algorithm continues to iterate through the process of finding the densest subgraph from the remaining input graph and adding it to the solution subgraph. Since in each iteration the algorithm adds the densest subgraph, it is ensured that the solution subgraph has sufficiently high density. Note that although we are able to prove that the algorithm guarantees a $3$-approximation ratio in terms of density, no bound on the size is guaranteed. We overcome this drawback by applying various simple heuristic algorithms which are described later in the section ~\ref{subsec:heuristic}.

{\it Details}: The algorithm {\it s-DensestAlk(G, {\cal T})}  takes as input the social graph $G$ and a task ${\cal T} = \{$<$a, k$>$\}$ where at least $k$ individuals/nodes of skill $a$ are required to perform the task ${\cal T}$. As explained intuitively, the algorithm then proceeds through multiple iterations. In each iteration, $i$, it finds the maximum density subgraph of $G_i$, say $H_{i+1}$, removes it from $G_i$ using the routine $shrink(G_i, H_{i+1})$ and constructs a new solution subgraph $D_{i+1}$ using the routine $union(D_i, H_{i+1})$. The routine $shrink(G, H)$ removes $H$ from $G$ such that for each $v \in (G - H)$, if $v$ has $l$ edges to the vertices in $H$, then it adds $l$ self-loops to $v$ with the corresponding edge-weights. Inside the routine $union(D, H)$, then for each loop, we look at its corresponding edge, say $e(u, v)$, in the original input graph, $G$, and if $u \in D, v\in H$ (or vice-versa), we replace the loop by an edge $e(u, v)$. Finally, once the loop-termination condition is satisfied, the algorithm then examines each of the intermediate solution subgraphs, $D_i$, constructed in previous iterations and adds sufficient number of skilled nodes to it so that each $D_i$ satisfies the skill requirement. The algorithm then picks up the one with the highest density as the final solution subgraph. 

Our algorithm is very similar to the {\it DensestAtleastK} algorithm in ~\cite{KS} that calculates the maximum density subgraph containing at least $k$ vertices without any skill constraints imposed. The naive extension would be to just add $k$ skilled nodes to the solution returned by algorithm {\it DensestAtleastK}. And since their algorithm guarantees an approximation factor of $2$ for density, this naive extension would guarantee an approximation factor of $4$ (proof omitted for brevity). But, since the additional $k$ nodes are picked at random the solution may suffer from many disconnected components making it practically infeasible to be of any use. Therefore, we propose the  algorithm {\it s-DensestAlk} that differs mainly in the loop-termination condition imposed. This condition ensures that the resulting solution satisfies the constraints of at least $k$ skilled nodes, improves the approximation ratio to $3$ from $4$, and has good connectivity properties.

Although the proof for $4$-approximation is simple, it turns out that proving a 3-approximation to {\it Density-sTF} is significantly harder. While the algorithm is simple, the analysis is fairly detailed. The key idea is to consider various cases about the returned subgraph and carefully examine the density of each component. The analysis is similar to~\cite{KS} at the high level. However, due to the skill-set constraints, several sub-cases need to be considered.
\begin{algorithm}[]
\caption{s-DensestAlk($G, {\cal T}$)}
\label{algo:sDlk}
\begin{algorithmic}[1]
\STATE $D_0  \leftarrow \phi, \ G_0 \leftarrow G, \ i \leftarrow 0$
\WHILE{ $|D_i \cap S(a)| < k$ where ${\cal T} = \{$<$a, k$>\}}
\STATE $H_{i + 1} \leftarrow$ maximum-density-subgraph$(G_i)$
\STATE $D_{i + 1} \leftarrow union(D_i, H_{i + 1})$
\STATE $G_{i + 1} \leftarrow shrink(G_i,  H_{i + 1})$
\STATE $i \leftarrow i + 1$
\ENDWHILE
\FOR {$each \ D_i$}
\STATE $n_a =$ number of nodes of skill $a$ in $D_i$
\STATE Add $max(k - n_a, 0)$ nodes of skill $a$ to $D_i$ to form $D'_i$
\ENDFOR
\STATE Return $D'_i$ which has the maximum density
\end{algorithmic}
\end{algorithm}
\begin{theorem}
The algorithm {\it s-DensestAlk} achieves an approximation factor of 3 for the {\it Density-sTF} problem.
\end{theorem}
\begin{proof}
\setcounter{equation}{0}
Let $H^*$ denote an optimal solution and $d^* =  \frac{W(H^*)}{|V(H^*)|}$ denote density of the optimal solution. 

If the number of iterations is 1, then $H_1$ is the maximum density subgraph that contains at least $k$ nodes of skill $a$. Therefore, $H^* = H_1$ and the algorithm returns it. Otherwise, say the algorithm iterates for $l \ge 2$ rounds. There can be two cases:

\noindent {\bf Case 1:} There exists an $l' < l$ such that \\
$W(D_{l' - 1} \cap H^*) < \frac{W(H^*)}{2}$  and  $W(D_{l'} \cap H^*) \ge \frac{W(H^*)}{2}$.

\begin{figure}[t]
\begin{center}
\includegraphics[scale=0.25, bb = 30 300 500 700]{3_approx_dia_1.eps}
\caption{$D_{l'} = D_{i1} \cup D_{i2} \cup X$}\label{fig:3approx}
\end{center}
\end{figure}

\noindent {\bf Case 2:} There exists no such $l' < l$.

Before analyzing the two cases in detail, note that by construction
$density(H_i) \le density(D_i) \le density(D_{i - 1})$. We now consider case 2 first and later case $1$.

\noindent {\bf Proof for Case 2.} 

Since the algorithm terminates after $l$ iterations, $D_l$ contains at least $k$ nodes of skill $a$. Further, we know that for each $j \le l - 1, W(D_j \cap  H^*)  < \frac{W(H^*)}{2}$ \\ 
$\Rightarrow W(G_j \cap  H^*)  \ge \frac{W(H^*)}{2}$ \\ 
$\Rightarrow \frac{W(G_j \cap H^*)}{|V(G_j \cap H^*)|} \ge \frac{W(H^*)}{2 |V(H^*)|}$ \\ 
$\Rightarrow G_j$ contains a subgraph of density $\ge \frac{d^*}{2}$ \\ 
$\Rightarrow density(H_l) \ge \frac{d^*}{2}$ \\ 
$\Rightarrow density(D_l) \ge \frac{d^*}{2}$

Thus, $D_l$ has density $\ge \frac{d^*}{2}$ and contains at least $k$ nodes of skill $a$. Therefore, the algorithm indeed returns a subgraph of density at least $\ge \frac{d^*}{2}$.

\noindent{\bf Proof for Case 1}

\noindent $W(D_{l' - 1} \cap H^*) < \frac{W(H^*)}{2}$  and  $W(D_{l'} \cap H^*) \ge \frac{W(H^*)}{2}$\\
$\Rightarrow W(G_{l'} \cap H^*) \ge \frac{W(H^*)}{2}$ where $G_{l'} = shrink(G, D_{l' -1})$ \\ 
$\Rightarrow \frac{W(G_{l'} \cap H^*)}{|V(G_{l'} \cap H^*)|} \ge \frac{W(H^*)}{2 |V(H^*)|} = \frac{d^*}{2}$ \\ 
$\Rightarrow G_{l'}$ has a subgraph of density $\ge \frac{d^*}{2}$ \\ 
$\Rightarrow density(H_{l'}) \ge \frac{d^*}{2}$  ($H_{l'}  \mbox { is densest subgraph of } G$) \\ 
$\Rightarrow density(D_{l'}) \ge \frac{d^*}{2}$

Now, let us divide {\bf Case 1} into following $4$ parts 
\begin{enumerate}[(a)]
\item $|V(D_{l'})| \le  \frac{k}{2}$ \\
According to step $10$, algorithm adds at most $k$ vertices to $D_{l'}$ to obtain the subgraph, say $D$, with density $d$\\
$d \ge \frac{W(D_{l'})}{|V(D_{l'})| + k} \ge \frac{\frac{W(H^*)}{2}}{\frac{k}{2} + k} \ge \frac{\frac{W(H^*)}{2}}{\frac{3 |V(H^*)|}{2}} = \frac{d^*}{3}$ 

\item $|V(D_{l'})| \ge  2k $

According to step $10$, algorithm adds at most $k$ vertices to $D_{l'}$. Further, we know that $density(D_{l'}) \ge \frac{d^*}{2}$ therefore, the resulting subgraph, $D'_{l'}$ has density 

\noindent $d = \frac{W(D_{l'})}{|V(D_{l'})| + k} \ge \frac{W(D_{l'})}{\frac{3}{2} |V(D_{l'})|}  \ge  \frac{d^*}{3}$

\item $\frac{k}{2} < |V(D_{l'})| <  2k$ and $ |V(D_{l'}) \cap V(H^*)| \ge \frac{|V(H^*)|}{2}$

According to step $10$, algorithm adds at most $\frac{|V(H^*)|}{2}$ nodes to $D_{l'}$ to form $D'_{l'}$ with density, say $d$.

\begin{enumerate}[i]
\item $|V(D_{l'})| \ge |V(H^*)|$ \\
$d \ge \frac{W(D_{l'})}{|V(D_{l'})| + \frac{|V(H^*)|}{2}} \ge \frac{W(D_{l'})}{|V(D_{l'})| + \frac{|V(D_{l'})|}{2}}  \ge \frac{d^*}{3}$ 

\item $|V(D_{l'})| < |V(H^*)|$ \\
$d \ge \frac{W(D_{l'})}{|V(D_{l'}|) + \frac{|V(H^*)|}{2}} \ge \frac{W(D_{l'})}{|V(H^*)| + \frac{|V(H^*)|}{2}} \ge  \frac{\frac{W(H^*)}{2}}{\frac{3}{2}|V(H^*)|} \ge \frac{d^*}{3}$
\end{enumerate} 

\item $\frac{k}{2} < |V(D_{l'})| <  2k$ and $|V(D_{l'}) \cap V(H^*)| < \frac{|V(H^*)|}{2}$

If $d_{l'} = density(D_{l'}) \ge d^*$, then adding at most $k$ vertices gives a subgraph $D'_{l'}$ with density, say $d$ such that

\noindent $d = \frac{W(D_{l'})}{ |V(D_{l'})| + k} \ge \frac{W(D_{l'})}{|V(D_{l'})| + 2 |V(D_{l'})|}  \ge \frac{W(D_{l'})}{3 |V(D_{l'})|} \ge \frac{d^*}{3}$

Therefore, $D_{l'}$ is a subgraph that contains at least $k$ nodes of skill $a$ and has density $d \ge \frac{d^*}{3}$. We are done here.

Now, assume that $d_{l'} < d^*$.

In the rest of the proof, we divide $D_{l'}$ into subgraphs as explained below and shown in Figure~\ref{fig:3approx}. 

$\mbox{Let } G' = D_{l'} \cap H^* $. 

\begin{claim}
\label{claim:case2Claim1}$W(G')\ge \frac{W(H^*)}{2}$ and $density(G')\ge d^*$.
\end{claim}
\begin{proof}
$|V(G')| = |V(D_{l'} \cap H^*)| < \frac{|V(H^*)|}{2} $ and $W(G') = W(D_{l'} \cap H^*) \ge  \frac{W(H^*)}{2} $. \\
$\Rightarrow density(G') \ge \frac{\frac{W(H^*)}{2}}{\frac{|V(H^*)|}{2}} \ge d^* $.
\end{proof}

Define $i$ such that $density(H_i)\ge d^*$ and $density(H_{i+1}) < d^*$. Such an $i\le l'$ exists due to {\sc Claim ~\ref{claim:case2Claim1}} and since $d_{l'} < d^*$.\\ 

$\Rightarrow density(D_i)  = d_i \ge d^*$. 

Let, $n_i = |V(D_i)| $. We now consider two sub-cases. 

\begin{enumerate}[i]
\item $n_i \ge \frac{|V(H^*)|}{2}$: Add at most $k$ vertices to $D_i$ to get a subgraph $D'_i$ with $density(D'_i) = d$, such that  \\
$d = \frac{W(D_i)}{|V(D_i)| + k} \ge \frac{W(D_i)}{|V(D_i)| + |V(H^*)|} \ge \frac{W(D_i)}{3 |V(D_i)|} \ge \frac{d^*}{3}$. \\ 
Thus, $D'_i$ is a subgraph containing at least $k$ nodes of skill $a$ and density $d \ge  \frac{d^*}{3}$ and we are done here.

\item $n_i < \frac{|V(H^*)|}{2}$:  
We know that $density(G') \ge  d^*$, $density(H_i) \ge d^*$ and $density(H_{i+1}) < d^*$.  Therefore, $G' \cap D_i \ne \phi$.
We now introduce a few definitions and prove claims about them. 

Let, $D_{i1} = D_i \cap G'$, $D_{i2} = shrink(D_i, D_{i1})$, and $G'' = shrink(G', D_{i1})$ (Figure: ~\ref{fig:3approx1}). Further, let $X = shrink(D_{l'}, D_i)$. \\

\begin{figure}[t]
\begin{center}
\includegraphics[scale=0.5, bb = 30 300 500 500]{3_approx_dia_2.eps} 
\caption{$D_{i1} = D_i \cap G'$, $D_{i2} = shrink(D_i, D_{i1})$, $G'' = shrink(G', D_{i1})$}\label{fig:3approx1}
\end{center}
\end{figure}

%CHANGE PREVIOUS FIGURE ALSO AND PLACE $X$ THERE. 

\begin{claim} 
\label{claim:case2Claim2}$W(D_{i1}) \ge  \frac{|V(H^*)| d^*}{2} - W(G'')$. 
\end{claim}
\begin{proof}
$W(G') = W(G'') + W(D_{i1})$ since $G'' = shrink(G', D_{i1})$; but $W(G')\ge \frac{W(H^*)}{2}$ (using {\sc Claim ~\ref{claim:case2Claim1}})
\end{proof}

\begin{claim}
\label{claim:case2Claim3} $density(D_{i2}) > \frac{d^*}{2}$.
\end{claim}
\begin{proof} 
Recall that for each $j \le i, density(H_j) > d^*$. Further, $H_j = \mbox{ densest subgraph of } shrink(G, D_{j-1})$.
Therefore, for each $v\in H_j$, the degree of $v$ induced in $H_j$ is at least $d^*$. Therefore, for all $v\in D_i$, $degree(v) > d^*$ (here we abuse notation to denote $v$'s degree induced in $D_{i}$ by $degree(v)$).
\end{proof}

For convenience, let $n_{x} = |V(X)|$, $n_{l'} = |V(D_{l'})|$, $n_{i1} = |V(D_{i1})|$, $n_{i2} = |V(D_{i2})|$, and $n'' = |V(G'')|$.

\begin{claim}
\label{claim:case2Claim4}$W(X) - W(G'') \ge \frac{d^*}{2} (n_{x} - n'')$.
\end{claim}
\begin{proof}
%Notice, $G'' \subseteq X$. 
Since $H_{l'}$ is the maximum density subgraph of $shrink(G, D_{l'-1})$, $density(H_{l'}) \ge density(S)$ for any $S \subseteq H_{l'},$. 
Further, since $X = shrink(D_{l'}, D_i)$, and $G'' = shrink(G', D_i \cap G')$, we have  $G'' \subseteq X$.
Therefore, $density(H_j) \ge density(H_j \cap G'')$ (for all $i < j \le l'$). \\
%Further, $X = H_{i+1} \cup H_{i + 2} \cup \cdot \cdot \cdot H_{l'} \Rightarrow G'' \subseteq X$ \\
Therefore, $W(X) - W(G'') $\\
$= \sum_{j=i+1}^{l'}{W(H_j)} - \sum_{j=i+1}^{l'}{W(H_{j} \cap G'')}$\\
%$= (W(H_{i+1}) + \cdot \cdot \cdot + W(H_{l'}) ) - (W(H_{i + 1} \cap G'') +\cdot \cdot \cdot +  W((H_{l'} \cap G'')$ \\
$\ge \sum_{j=i+1}^{l'}{density(H_{j}) (\mid H_{j} \mid - \mid H_{j} \cap G'' \mid)}$\\
%$\ge density(H_{i + 1}) (\mid H_{i+1} \mid - \mid H_{i + 1} \cap G'' \mid) + \cdot \cdot \cdot + density(H_{l'}) (\mid H_{l'} \mid - \mid H_{l'} \cap G'' \mid) $
$\ge \frac{d^*}{2} (n_x - n'')$.
\end{proof}

Notice that we have (lower) bounded the density or the weight of each of $D_{i1}$, $D_{i2}$, and $X$, the three components that add up to $D_{l'}$. We are now ready to argue about the density of $D_{l'}$ when $k$ vertices are added to it. Before initiating this analysis, we briefly state a claim relating the sizes of these components. 

\begin{claim}
\label{claim:case2Claim5}$n_{i2} + n_x - n''\ge n_{l'} - \frac{|V(H^*)|}{2}$
\end{claim}
\begin{proof}
This follows using $|V(G')|  \le \frac{|V(H^*)|}{2}$ and the definition $G'' = shrink(G', D_{i1})$.
\end{proof}

We now complete the analysis. \\  

\noindent $d = density(D) \ge \frac{W(D_{l'})}{n_{l'} + k}$ \\
$= \frac{W(D_i) + W(X)}{n_{l'} + k} = \frac{W(D_{i1}) + W(D_{i2}) + W(X)}{n_{l'} + k}$ \\ 
$\ge \frac{\frac{d^* |V(H^*)|}{2} - W(G'') + \frac{d^*n_{i2}}{2} + W(X)}{n_{l'} + k}$ (using {\sc Claim ~\ref{claim:case2Claim2},~\ref{claim:case2Claim3}})\\ 
$\ge \frac{\frac{d^* |V(H^*)|}{2} + \frac{d^*n_{i2}}{2} + \frac{d^*}{2}(n_x - n'')}{n _{l'}+ k}$ (using {\sc Claim ~\ref{claim:case2Claim4}})\\ 
$\ge \frac{d^*}{2} \frac{|V(H^*)| + n_{l'} - \frac{|V(H^*)|}{2}}{n_{l'} + k}$ (using {\sc Claim ~\ref{claim:case2Claim5}}) \\ 
$\ge \frac{d^*}{4} \frac{2n_{l'} + k}{n_{l'} + k} \ge \frac{d^*}{3}$ (since $\frac{k}{2} < n_{l'}$).
\end{enumerate}
\end{enumerate} 
Remark: Cases (c) and (d) do not use the bound $|V(D_{l'}) < 2k|$; so they together subsume case (b), but we have presented (b) for clarity.
\end{proof}

\subsection{Algorithm for {\it Density-mTF}}
In this section, we present the algorithm {\it m-DensestAlk} (Algorithm ~\ref{algo:mDlk}) for the {\it Density-mTF} problem. This is an extension of the algorithm {\it s-DensestAlk} for the {\it Density-sTF} problem described earlier. The algorithm {\it m-DensestAlk} accepts input parameters: graph $G$ and  task ${\cal T} = \{<a_1, k_1>, <a_2, k_2>, \ldots, <a_m, k_m>\}$  which requires at least $k_i$ individuals of skill $a_i$ to perform the task $\cal T$. Each iteration within the algorithm {\it m-DensestAlk} is exactly similar to the {\it s-DensestAlk} described earlier except that here the termination condition verifies that the solution subgraph contains at least $k_i$ nodes with skill $a_i$ for $i \in \{ 1 \cdot \cdot m \}$ and thus satisfying the {\it multiple} skill requirement instead of {\it single} skill requirement. The details of the algorithm are similar to that described for {\it s-DensestAlk} in the section ~\ref{subsec:density-sTF}.
\begin{algorithm}[]
\caption{m-DensestAlk($G, {\cal T}$)}
\label{algo:mDlk}
\begin{algorithmic}[1]
\STATE $D_0  \leftarrow \phi, \ G_0 \leftarrow G, \ i \leftarrow 0$
\WHILE{ $|D_i \cap S(a_j)| < k_j$ for any $<a_j, k_j> \in {\cal T}$}
\STATE $H_{i + 1} \leftarrow$ maximum-density-subgraph$(G_i)$
\STATE $D_{i + 1} \leftarrow union(D_i, H_{i + 1})$
\STATE $G_{i + 1} \leftarrow shrink(G_i,  H_{i + 1})$
\STATE $i \leftarrow i + 1$
\ENDWHILE
\FOR {$each \ D_i$}
\STATE $D'_i \leftarrow D_i$
\FOR {$each \ <a_1, k_1> \in {\cal T}$}
\STATE $n_{aj} =$ number of nodes of skill $a_j$ in $D_i$
\STATE Add $max(k_j - n_{aj}, 0)$ nodes of skill $a_j$ to $D'_i$
\ENDFOR
\ENDFOR
\STATE Return $D'_i$ which has the maximum density
\end{algorithmic}
\end{algorithm}
\begin{theorem}
The algorithm {\it m-DensestAlk} achieves an approximation factor of 3 for the special case of {\it Density-mTF} problem where each node in the graph has at most one skill.
\end{theorem}
\begin{proof}
Let $m =\ \mid${\cal T}$\mid$ and $k = \sum_{j=1}^{m}{k_j}$ where $k_j$ number of individuals are required of skill $a_j$ s.t. $<a_j,k_j> \in {\cal T}$. Since each node contributes to atmost one skill, an optimal solution, $H^*$, has at least $k$ vertices. The proof for {\it m-DensestAlk} is analogous to the proof for {\it s-DensestAlk} with the only difference that instead of adding any $k$ nodes of skill $a$ to $D_i$s, we add $k_j$ nodes of skill $a_j$ s.t. $<a_j,k_j> \in {\cal T}$.
\end{proof}

We are unable to bound the performance of {\it m-DensestAlk} for the general case of {\it Density-mTF} problem. Futher, the time complexity of {\it m-DensestAlk} is $O(k n^3)$ which can be inefficient for very large graphs but is manageable at the scale at which we run experiments. Directly using the linear time algorithm for the densest at least $k$ subgraph problem in~\cite{KS,AC} or $O(n^3)$-time algorithm from~\cite{KS,AC} for {\it Density-sTF} problem would result in a weaker bound i.e. $6$ and $4$-approximation respectively. In both cases, however, one may possibly get many disconnected components.

% There is a linear time 3-approximation algorithm for the densest at least $k$ subgraph problem suggested in~\cite{KS,AC} but this would only translate to a $6$-approximation algorithm for {\it Density-sTF}. Similarly, directly using the $O(n^3)$-time $2$-approximation algorithm %from~\cite{KS,AC} would also result in a weaker bound (i.e. $4$-approximation). In both cases, one may possibly get many disconnected components.
